A64 - Shortest Path 2 - 競プロ

A64 - Shortest Path 2

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bl

解答

code: python

import heapq

N, M = map(int, input().split())

edges = list(map(int, input().split())) for i in range(M)

# (隣接頂点, 重み)

g = list() for i in range(N + 1)

for a, b, c in edges:

ga.append((b, c))

gb.append((a, c))

INF = 10 ** 10

# 確定した点かどうか

fixed = False * (N + 1)

# 暫定値

ans = INF * (N + 1)

ans1 = 0

next = []

# (暫定値, 頂点)

heapq.heappush(next, (0, 1))

while len(next) >= 1:

# 次に確定させるべき頂点を求める

# ここでは、優先度付きキュー next の最小要素を取り除き、その要素の 2 番目の値（頂点番号）を now に代入する

# 小さいのを選べば自ずと確定していく

now = heapq.heappop(next)1

if fixednow:

continue

# ansx の値を更新する

fixednow = True

for v in gnow:

tyouten = v0

omomi = v1

if anstyouten > ansnow + omomi:

anstyouten = ansnow + omomi

heapq.heappush(next, (anstyouten, tyouten))

for i in range(1, N + 1):

if ansi != INF:

print(ansi)

else:

print("-1")